package 数组.下一个更大元素;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/2/16 17:19
 * @description:
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        int[] array1 = {4,1,2};
        int[] array2 = {1,3,4,2};
        int[] ints = nextGreaterElement2(array1, array2);

    }

    //暴力算法，待优化
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int length = nums1.length;
        int[] result = new int[length];
        for (int i = 0; i < nums1.length; i++) {
            int target = nums1[i];
            for (int j = 0; j < nums2.length; j++) {
                if (nums2[j] == target){
                    for (int k = j+1; k < nums2.length; k++) {
                        if (nums2[k] > target){
                            result[i] = nums2[k];
                            break;
                        }
                    }
                }
            }
        }
        for (int i = 0; i < result.length; i++) {
            if (result[i] == 0){
                result[i] = -1;
            }
        }

        return result;
    }

    //借助hashmap来进行优化
    public static int[] nextGreaterElement2(int[] nums1, int[] nums2){
        int length = nums1.length;
        int[] result = new int[length];
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums2.length; i++) {
            map.put(nums2[i],i);
        }

        for (int i = 0; i < nums1.length; i++) {
            Integer index = map.get(nums1[i]);
            for (int j = index; j < nums2.length; j++) {
                if (nums2[j] > nums1[i]){
                    result[i] = nums2[j];
                    break;
                }
            }
            if (result[i] == 0){
                result[i] = -1;
            }
        }
        return result;
    }
}
